/**
C++ 树（二叉树）模板和测试
*/

#include <iostream>
#include <vector>

template <typename T>
class TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

/**
管理二叉树的根节点，实现一些操作
*/
template <typename T>
class BinaryTree {
   private:
    TreeNode<T>* root;

    // 辅助函数：递归插入
    TreeNode<T>* insertRecursive(TreeNode<T>* node, T val) {
        if (node == nullptr) {
            return new TreeNode<T>(val);
        }

        if (val < node->data) {
            node->left = insertRecursive(node->left, val);
        } else if (val > node->data) {
            node->right = insertRecursive(node->right, val);
        }
        // 如果值等于节点数据，我们通常不插入重复值或根据需求处理

        return node;
    }

    // 辅助函数：递归查找
    // 中序遍历查找
    TreeNode<T>* searchRecursive(TreeNode<T>* node, T val) {
        if (node == nullptr || node->data == val) {
            return node;
        }

        if (val < node->data) {
            return searchRecursive(node->left, val);
        } else {
            return searchRecursive(node->right, val);
        }
    }

    // 辅助函数：中序遍历（递归）
    void inorderTraversalRecursive(TreeNode<T>* node) {
        if (node == nullptr) {
            return;
        }
        inorderTraversalRecursive(node->left);
        std::cout << node->data << " ";
        inorderTraversalRecursive(node->right);
    }

    // 辅助函数：删除所有节点（递归，用于析构函数）
    void destroyRecursive(TreeNode<T>* node) {
        if (node) {
            destroyRecursive(node->left);
            destroyRecursive(node->right);
            delete node;
        }
    }

   public:
    // 构造函数
    BinaryTree() : root(nullptr) {}

    // 析构函数：释放所有节点内存
    ~BinaryTree() { destroyRecursive(root); }

    // 公共接口：插入
    void insert(T val) { root = insertRecursive(root, val); }

    // 公共接口：查找
    bool search(T val) { return searchRecursive(root, val) != nullptr; }

    // 公共接口：中序遍历
    void inorderTraversal() {
        inorderTraversalRecursive(root);
        std::cout << std::endl;
    }

    // 可选：获取根节点（如果需要从外部访问）
    TreeNode<T>* getRoot() const { return root; }
};